package com.xj.datastructure.sort;

/**
 * author: xiajun
 * Date: 2014-07-19
 * Time: 16-58-00
 * 通常堆是通过一维数组来实现的。在起始数组为 0 的情形中：
 * 父节点i的左子节点在位置 (2*i+1);
 * 父节点i的右子节点在位置 (2*i+2);
 * 子节点i的父节点在位置 floor((i-1)/2);
 */
public class HeapSort {
    public static void main(String[] args) {
        int a[] = {2, 4, 42, 43, 145, 211, 34, 7, 3, 56, 85};
        HeapSort sort = new HeapSort();
        sort.createHeap(a);
        sort.print(a);
    }

    public void createHeap(int[] a) {
        int pIndex = prentIndex(a.length - 1);
        for (int i = pIndex; i >= 0; i--) {
            minHeap(a, a.length, i);
        }
        System.out.println("----------->"+a[0]);
        heapSort(a);
    }

    public void minHeap(int[] a, int heapSize, int current) {
        int left = leftClientIndex(current);
        int right = rightClientIndex(current);
        int index = current;
        if (left < heapSize && a[left] < a[current]) {
            index = left;
        }
        if (right < heapSize && a[right] < a[index]) {
            index = right;
        }
        if (index != current) {
            int tmp = a[index];
            a[index] = a[current];
            a[current] = tmp;
            minHeap(a, heapSize, index);
        }
    }

    public void heapSort(int[] a) {
        for (int i = a.length - 1; i > 0; i--) {
            int tmp = a[0];
            a[0] = a[i];
            a[i] = tmp;
            minHeap(a, i, 0);
        }
    }

    public void print(int[] a) {
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }
    }

    public int leftClientIndex(int parent) {
        return (parent << 1) + 1;
    }

    public int rightClientIndex(int parent) {
        return (parent << 1) + 2;
    }

    public int prentIndex(int current) {
        return (current - 1) >> 1;
    }
}
